<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="theme-color" content="black"><meta name="author" content="李子康"><meta name="copyright" content="李子康"><meta name="generator" content="Hexo 4.2.1"><meta name="theme" content="hexo-theme-yun"><title>数据结构 第四讲 树的基本概念、二叉树、树和森林 | Lizikang_Blog</title><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@900&amp;display=swap" media="none" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/star-markdown-css@0.1.11/dist/yun/yun-markdown.min.css"><script src="//at.alicdn.com/t/font_1140697_stqaphw3j4.js" async></script><script src="https://cdn.jsdelivr.net/npm/scrollreveal/dist/scrollreveal.min.js" defer></script><script>document.addEventListener("DOMContentLoaded", () => {
  [".post-card",".post-content img"].forEach((target)=> {
    ScrollReveal().reveal(target);
  })
});
</script><script src="https://cdn.jsdelivr.net/npm/pjax@latest/pjax.min.js" defer></script><script src="/js/pjax.js" defer></script><link rel="shortcut icon" type="image/svg+xml" href="/images/%E7%9A%AE%E5%8D%A1%E4%B8%98-2.ico"><link rel="mask-icon" href="/images/%E7%9A%AE%E5%8D%A1%E4%B8%98-2.ico" color="black"><link rel="alternate icon" href="/yun.ico"><link rel="preload" href="/css/hexo-theme-yun.css" as="style"><link rel="preload" href="/js/utils.js" as="script"><link rel="preload" href="/js/hexo-theme-yun.js" as="script"><link rel="prefetch" href="/js/sidebar.js" as="script"><link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin><link rel="stylesheet" href="/css/hexo-theme-yun.css"><link rel="alternate" href="/atom.xml" title="Lizikang_Blog"><script id="yun-config">
    const Yun = window.Yun || {};
    window.CONFIG = {"root":"/","title":["Li","Zi","Kang","Blog"],"version":"0.9.2","anonymous_image":"https://cdn.jsdelivr.net/gh/YunYouJun/cdn/img/avatar/none.jpg","say":{"api":"https://v1.hitokoto.cn","hitokoto":true},"fireworks":{"colors":["102, 167, 221","62, 131, 225","33, 78, 194"]}};
  </script><script src="//at.alicdn.com/t/font_1929835_1z6thct9lfe.js" async></script><meta name="description" content="第四讲 树的基本概念、二叉树、树和森林1. 树的基本概念(1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。(2) 空集合也是树，称为空树。空树中没有节点；(3) 孩子节点或子节点：一个节">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构 第四讲 树的基本概念、二叉树、树和森林">
<meta property="og:url" content="http://yoursite.com/2021/07/18/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_4_1/index.html">
<meta property="og:site_name" content="Lizikang_Blog">
<meta property="og:description" content="第四讲 树的基本概念、二叉树、树和森林1. 树的基本概念(1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。(2) 空集合也是树，称为空树。空树中没有节点；(3) 孩子节点或子节点：一个节">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716201142018.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716203738956.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716203854415.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716204207520.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716213705277.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210717135246087.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210717135737523.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718164805299.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718165530244.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718165949376.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170017054.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170548173.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170726674.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170914309.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718171711486.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718172227150.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718194045253.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726210106380.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718194140386.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718194216798.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211221536.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211338689.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211528316.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211558663.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211658422.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211724679.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211824779.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211910620.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726212632926.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726212650654.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211931557.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211951141.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726213032648.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726213120328.png">
<meta property="og:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726215002976.png">
<meta property="article:published_time" content="2021-07-17T16:00:00.000Z">
<meta property="article:modified_time" content="2021-08-25T06:29:13.723Z">
<meta property="article:author" content="李子康">
<meta property="article:tag" content="数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716201142018.png"><script src="/js/ui/mode.js"></script><link rel="alternate" href="/atom.xml" title="Lizikang_Blog" type="application/atom+xml">
</head><body><script defer src="https://cdn.jsdelivr.net/npm/animejs@latest/anime.min.js"></script><script defer src="/js/ui/fireworks.js"></script><canvas class="fireworks"></canvas><div class="container"><a class="sidebar-toggle hty-icon-button" id="menu-btn"><div class="hamburger hamburger--spin" type="button"><span class="hamburger-box"><span class="hamburger-inner"></span></span></div></a><div class="sidebar-toggle sidebar-overlay"></div><aside class="sidebar"><script defer src="/js/sidebar.js"></script><ul class="sidebar-nav"><li class="sidebar-nav-item sidebar-nav-toc hty-icon-button sidebar-nav-active" data-target="post-toc-wrap" title="文章目录"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-list-ordered"></use></svg></li><li class="sidebar-nav-item sidebar-nav-overview hty-icon-button" data-target="site-overview-wrap" title="站点概览"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-passport-line"></use></svg></li></ul><div class="sidebar-panel" id="site-overview-wrap"><div class="site-info fix-top"><a class="site-author-avatar" href="/about/" title="李子康"><img width="96" loading="lazy" src="/images/bak.jpg" alt="李子康"></a><div class="site-author-name"><a href="/about/">李子康</a></div><a class="site-name" href="/about/site.html">Lizikang_Blog</a><sub class="site-subtitle"></sub><div class="site-desciption">个人技术博客</div></div><nav class="site-state"><a class="site-state-item hty-icon-button icon-home" href="/" title="我的主页"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-home-4-line"></use></svg></span></a><div class="site-state-item"><a href="/archives/" title="归档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-archive-line"></use></svg></span><span class="site-state-item-count">27</span></a></div><div class="site-state-item"><a href="/categories/" title="分类"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-2-line"></use></svg></span><span class="site-state-item-count">13</span></a></div><div class="site-state-item"><a href="/tags/" title="标签"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="site-state-item-count">9</span></a></div><a class="site-state-item hty-icon-button" href="https://yun.yunyoujun.cn" target="_blank" rel="noopener" title="文档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-settings-line"></use></svg></span></a></nav><hr style="margin-bottom:0.5rem"><div class="links-of-author"><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://wpa.qq.com/msgrd?v=3&amp;uin=1191787635&amp;site=qq&amp;menu=yes" title="QQ" target="_blank" style="color:#12B7F5"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-qq-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://github.com/lizikanglzk" title="GitHub" target="_blank" style="color:#181717"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-github-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="mailto:1191787635@qq.com" title="E-Mail" target="_blank" style="color:#8E71C1"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-mail-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://gitee.com/li_zikang" title="gitee" target="_blank" style="color:#E6162D"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-gitee-copy"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://music.163.com/#/user/home?id=506556053" title="网易云音乐" target="_blank" style="color:#C10D0C"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-netease-cloud-music-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://blog.csdn.net/qq_43845915" title="csdn" target="_blank" style="color:#007722"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-csdn11"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://www.zhihu.com/people/zou-guo-lu-guo-bu-yao-cuo-guo-88" title="知乎" target="_blank" style="color:#0084FF"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-zhihu-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://space.bilibili.com/352594163" title="哔哩哔哩动画" target="_blank" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-bilibili-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" title="微信" target="_blank" style="color:#1AAD19"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-wechat-2-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="/atom.xml" title="RSS" target="_blank" style="color:orange"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-rss-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="/game1" title="Telegram Channel" target="_blank" style="color:#0088CC"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-youxi-copy-copy"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://travellings.now.sh/" title="Travelling" target="_blank" style="color:var(--hty-text-color)"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-send-plane-2-line"></use></svg></a></div><hr style="margin:0.5rem 1rem"><div class="links"><a class="links-item hty-icon-button" href="/links/" title="我的小伙伴们" style="color:dodgerblue"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-men-line"></use></svg></a><a class="links-item hty-icon-button" href="/girls/" title="我的老婆们" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-women-line"></use></svg></a></div><br><a class="links-item hty-icon-button" id="toggle-mode-btn" href="javascript:;" title="Mode" style="color: #f1cb64"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-contrast-2-line"></use></svg></a></div><div class="sidebar-panel sidebar-panel-active" id="post-toc-wrap"><div class="post-toc"><div class="post-toc-content"><ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#第四讲-树的基本概念、二叉树、树和森林"><span class="toc-text">第四讲 树的基本概念、二叉树、树和森林</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-树的基本概念"><span class="toc-text">1. 树的基本概念</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-二叉树"><span class="toc-text">2. 二叉树</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3-树、森林"><span class="toc-text">3. 树、森林</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4"><span class="toc-text">4. 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#5-押题：AcWing-19"><span class="toc-text">5. 押题：AcWing 19</span></a></li></ol></li></ol></div></div></div></aside><main class="sidebar-translate" id="content"><div id="post"><article class="post-block" itemscope itemtype="https://schema.org/Article"><link itemprop="mainEntityOfPage" href="http://yoursite.com/2021/07/18/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_4_1/"><span hidden itemprop="author" itemscope itemtype="https://schema.org/Person"><meta itemprop="name" content="李子康"><meta itemprop="description"></span><span hidden itemprop="publisher" itemscope itemtype="https://schema.org/Organization"><meta itemprop="name" content="Lizikang_Blog"></span><header class="post-header"><h1 class="post-title" itemprop="name headline">数据结构 第四讲 树的基本概念、二叉树、树和森林</h1><div class="post-meta"><div class="post-time" style="display:inline-block"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-line"></use></svg></span> <time title="创建时间：2021-07-18 00:00:00" itemprop="dateCreated datePublished" datetime="2021-07-18T00:00:00+08:00">2021-07-18</time><span class="post-meta-divider">-</span><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-2-line"></use></svg></span> <time title="修改时间：2021-08-25 14:29:13" itemprop="dateModified" datetime="2021-08-25T14:29:13+08:00">2021-08-25</time></div><span class="post-busuanzi"><span class="post-meta-divider">-</span><span class="post-meta-item-icon" title="阅读次数"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-eye-line"></use></svg> <span id="busuanzi_value_page_pv"></span></span></span><div class="post-classify"><span class="post-category"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-line"></use></svg></span> <span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">数据结构</span></a></span> > <span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">acwing</span></a></span></span><span class="post-tag"><span class="post-meta-divider">-</span><a class="tag" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">数据结构</span></a></span></div></div></header><section class="post-body" itemprop="articleBody"><div class="post-content markdown-body" style="--smc-primary:black;"><h3 id="第四讲-树的基本概念、二叉树、树和森林"><a href="#第四讲-树的基本概念、二叉树、树和森林" class="headerlink" title="第四讲 树的基本概念、二叉树、树和森林"></a>第四讲 树的基本概念、二叉树、树和森林</h3><h4 id="1-树的基本概念"><a href="#1-树的基本概念" class="headerlink" title="1. 树的基本概念"></a>1. 树的基本概念</h4><p>(1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。<br>(2) 空集合也是树，称为空树。空树中没有节点；<br>(3) 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；<br>(4) 节点的度：一个节点含有的子节点的个数称为该节点的度；<br>(5) 叶节点或终端节点：度为0的节点称为叶节点；<br>(6) 非终端节点或分支节点：度不为0的节点；<br>(7) 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；<br>(8) 兄弟节点：具有相同父节点的节点互称为兄弟节点；<br>(9) 树的度：一棵树中，最大的节点的度称为树的度；<br>(10) 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；<br>(11) 树的高度或深度：树中节点的最大层次；<br>(12) 节点的祖先：从根到该节点所经分支上的所有节点；<br>(13) 子孙：以某节点为根的子树中任一节点都称为该节点的子孙；<br>(14) 森林：由棵互不相交的树的集合称为森林。</p>
<blockquote>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716201142018.png" alt="image-20210716201142018" loading="lazy"></p>
<p>理解理解理解</p>
</blockquote>
<h4 id="2-二叉树"><a href="#2-二叉树" class="headerlink" title="2. 二叉树"></a>2. 二叉树</h4><p>(1) 二叉树的定义及其主要特征<br>    a. 二叉树的基本形态：空二叉树、单节点二叉树、左子树、右子树</p>
<p>​    b. 性质：</p>
<p>​    [1] 在非空二叉树中，第i层上至多有2^(i-1) 个结点。<br>​    [2] 深度为k的二叉树至多有2^k - 1个结点<br>​    [3] 对任何一颗二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。<br>​    [4] n个结点的完全二叉树深度为：log2(n)向下取整 + 1<br>​    [5] 二叉树的堆式存储: 节点p (编号p)的左儿子：2p，右儿子：2p+1<br>​<br>​        //  r = [p/2]下取整</p>
<p>​    c. 两种特殊的二叉树<br>​        [1] 满二叉树：一颗深度为k且有2^k-1个结点的二叉树<br>​        [2] 如果深度为k,有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树</p>
<p>(2) 二叉树的顺序存储结构和链式存储结构</p>
<p>​    链式存储结构<br>​    /**c++:<br>​     * Definition for a binary tree node.<br>​     * struct TreeNode {<br>​     *     int val;<br>​     *     TreeNode *left;<br>​     *     TreeNode *right;<br>​     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}<br>​     * };<br>​     */<br>​     </p>
<p>(3) 二叉树的遍历<br>    a. 前序遍历  dfs<br>    b. 中序遍历<br>    c. 后序遍历<br>    d. 根据前序 + 中序重建二叉树 (AcWing 18. 重建二叉树)<br>    层次遍历不考 bfs </p>
<p>​        </p>
<p>(4) 线索二叉树的基本概念和构造<br>​        对二叉树节点的指针域做如下规定：<br>​            a. 若节点有左孩子，则Lchild指向左孩子，否则指向直接前驱；右孩子同理；<br>​            b. 增加两个标志域，Ltag表示指向的是子节点还是前驱；Rtag同理<br>​            c. 指向前驱和后继的指针叫做线索。按照某种次序遍历，加上线索的二叉树称之为线索二叉树</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716203738956.png" alt="image-20210716203738956" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716203854415.png" alt="image-20210716203854415" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716204207520.png" alt="image-20210716204207520" loading="lazy"></p>
<blockquote>
<p><strong>n  = n0 + n1 + n2</strong></p>
<p>n-1边</p>
<p><strong>n-1 = 0<em>n0 + 1 * n1 + 2</em>n 2</strong></p>
<p>n0 + n1 + n2 - 1 == 0<em>n0 + 1 * n1 + 2</em>n 2</p>
<p>n0  - 1 ==   n 2</p>
<p><strong>n0 = n2 + 1</strong> </p>
<p>1 </p>
<p>前序+中序 —&gt;&gt; 构造二叉树</p>
</blockquote>
<h4 id="3-树、森林"><a href="#3-树、森林" class="headerlink" title="3. 树、森林"></a>3. 树、森林</h4><p>(1) 树的存储结构<br>    a. 只存父节点<br>    b. 邻接表存储所有子节点<br>    c. 左儿子右兄弟<br>(2) <strong>森林F</strong>与<strong>二叉树T</strong>的转换<br>    a. <strong>原树中叶子节点数 = 转换后的树中有右儿子的节点数 + 1</strong><br>    b. <strong>F的前序遍历</strong>就是<strong>T的前序遍历</strong><br>    c. <strong>F的后序遍历</strong>就是<strong>T的中序遍历</strong><br>(3) 树和森林的遍历<br>    a. 前序遍历<br>    b. 后序遍历</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210716213705277.png" alt="image-20210716213705277" loading="lazy"></p>
<h4 id="4-考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4"><a href="#4-考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4" class="headerlink" title="4. 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4"></a>4. 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4</h4><p><strong>2011-4</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210717135246087.png" alt="image-20210717135246087" loading="lazy"></p>
<blockquote>
<p>分析：求叶节点 n0 </p>
<p>768 = n0+n1+n2</p>
<p>n0 = n2+1 ;</p>
<p>2*n2 +1 + n1 = 768</p>
<p>768 为偶数 n1 =1 ，多一个</p>
<p>2*n2 = 766</p>
<p>n2 = 383</p>
<p>n0 = n2+ 1 = 384 ;</p>
</blockquote>
<p><strong>2011-5</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210717135737523.png" alt="image-20210717135737523" loading="lazy"></p>
<blockquote>
<p>前序和后序遍历 不能唯一确定 树</p>
<p>选择题 可以用 前序和 中序来判断</p>
</blockquote>
<p><strong>2011-6</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718164805299.png" alt="image-20210718164805299" loading="lazy"></p>
<blockquote>
<p>用结论 :  <strong>原树中叶子节点数 = 转换后的树中有右儿子的节点数 + 1</strong>  </p>
<p>树中有右儿子的节点数   116 == 115 + 1 </p>
<p>2011 - 115 = 1896</p>
</blockquote>
<p><strong>2012-3</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718165530244.png" alt="image-20210718165530244" loading="lazy"></p>
<blockquote>
<p>A</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718165949376.png" alt="image-20210718165949376" loading="lazy"></p>
</blockquote>
<p><strong>2013-5</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170017054.png" alt="image-20210718170017054" loading="lazy"></p>
<blockquote>
<p>A</p>
<p><strong>后序线索二叉树</strong>：看<strong>后序遍历</strong> </p>
<p>线索二叉树：若节点有左孩子，则Lchild指向左孩子，否则指向直接前驱；右孩子同理</p>
<p>X 有 左兄弟 ，为叶节点 没有孩子</p>
<p>指向直接前驱 x 的父节点     yxp </p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170548173.png" alt="image-20210718170548173" loading="lazy"></p>
</blockquote>
<p><strong>2014-4</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170726674.png" alt="image-20210718170726674" loading="lazy"></p>
<blockquote>
<p>中序线索化：看中序遍历</p>
<p>debxac</p>
<p>选D</p>
</blockquote>
<p><strong>2014-5</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718170914309.png" alt="image-20210718170914309" loading="lazy"></p>
<blockquote>
<p>森林&gt;&gt;二叉树  左儿子 右兄弟</p>
<p>兄弟 == 儿子？ yes</p>
<p>叶节点： 没有孩子</p>
<p>所以为没有左孩子的</p>
<p>选C</p>
</blockquote>
<p><strong>2014-41</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718171711486.png" alt="image-20210718171711486" loading="lazy"></p>
<blockquote>
<p>带权路径  ： 权值* 到根节点的距离</p>
<p><a href="https://www.acwing.com/problem/content/3769/" target="_blank" rel="noopener"><strong>AcWing 3766. 二叉树的带权路径长度</strong></a>    </p>
<p>树的遍历 ， 推荐dfs实现 即递归</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718172227150.png" alt="image-20210718172227150" loading="lazy"></p>
</blockquote>
<p>C++:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * Definition for a binary tree node.</span><br><span class="hljs-comment"> * struct TreeNode &#123;</span><br><span class="hljs-comment"> *     int val;</span><br><span class="hljs-comment"> *     TreeNode *left;</span><br><span class="hljs-comment"> *     TreeNode *right;</span><br><span class="hljs-comment"> *     TreeNode(int x) : val(x), left(NULL), right(NULL) &#123;&#125;</span><br><span class="hljs-comment"> * &#125;;</span><br><span class="hljs-comment"> */</span><br><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span><br><span class="hljs-keyword">public</span>:<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dfs</span><span class="hljs-params">(TreeNode* root,<span class="hljs-keyword">int</span> depth)</span></span>&#123;  <span class="hljs-comment">// depth 为深度</span><br>     <span class="hljs-keyword">if</span>(!root) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;   <span class="hljs-comment">//如果是空</span><br>     <span class="hljs-comment">// 如果是叶节点: 没有左右孩子</span><br>     <span class="hljs-keyword">if</span>(!root-&gt;left&amp;&amp;!root-&gt;right) <span class="hljs-keyword">return</span> root-&gt;val*depth; <br>     <span class="hljs-keyword">else</span> &#123;<br>         <span class="hljs-comment">// 左右遍历 返回左右子树权值</span><br>         <span class="hljs-keyword">return</span> dfs(root-&gt;left,depth+<span class="hljs-number">1</span>)+ dfs(root-&gt;right,depth+<span class="hljs-number">1</span>);<br>         <br>     &#125;<br>     <br>    &#125;<br><br><br>    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">pathSum</span><span class="hljs-params">(TreeNode* root)</span> </span>&#123;<br>        <br>        <span class="hljs-keyword">return</span> dfs(root , <span class="hljs-number">0</span>);<br>    &#125;<br>&#125;;<br></code></pre></td></tr></table></figure>

<p>c:</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><code class="hljs c"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * Definition for a binary tree node.</span><br><span class="hljs-comment"> * struct TreeNode &#123;</span><br><span class="hljs-comment"> *     int val;</span><br><span class="hljs-comment"> *     struct TreeNode *left;</span><br><span class="hljs-comment"> *     struct TreeNode *right;</span><br><span class="hljs-comment"> * &#125;;</span><br><span class="hljs-comment"> */</span><br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">dfs</span><span class="hljs-params">(struct TreeNode* root,<span class="hljs-keyword">int</span> depth)</span></span>&#123;<br>    <br>    <span class="hljs-keyword">if</span>(!root ) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">if</span>(!root-&gt;left&amp;&amp;!root-&gt;right) <span class="hljs-keyword">return</span> root-&gt;val*depth;<br>    <span class="hljs-keyword">else</span>&#123;<br>        <br>        <span class="hljs-keyword">return</span> dfs(root-&gt;left,depth+<span class="hljs-number">1</span>)+ dfs(root-&gt;right,depth+<span class="hljs-number">1</span>);<br>        <br>    &#125;<br>    <br>&#125; <br> <br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">pathSum</span><span class="hljs-params">(struct TreeNode* root)</span> </span>&#123;<br>    <br>    <br><span class="hljs-keyword">return</span> dfs(root , <span class="hljs-number">0</span>);<br><br>    <br>&#125;<br></code></pre></td></tr></table></figure>



<p><strong>2015-2</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718194045253.png" alt="image-20210718194045253" loading="lazy"></p>
<blockquote>
<p> 包含4个点的二叉树数量</p>
<p> N 卡特兰数</p>
<p> <img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726210106380.png" alt="image-20210726210106380" loading="lazy"></p>
</blockquote>
<p><strong>2016-5</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718194140386.png" alt="image-20210718194140386" loading="lazy"></p>
<blockquote>
<p>25个结点 24条边</p>
<p>每删一条边多一颗树 </p>
<p>删了24 - 15 = 9 棵</p>
<p>9+1 = 10 棵</p>
</blockquote>
<p><strong>2016-42</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210718194216798.png" alt="image-20210718194216798" loading="lazy"></p>
<blockquote>
<p>1.</p>
<p>归纳法：</p>
<p>n  =  nk+ n0</p>
<p>e  = k* nk</p>
<p>e  =  n - 1</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211221536.png" alt="image-20210726211221536" loading="lazy"></p>
<p>2.</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211338689.png" alt="image-20210726211338689" loading="lazy"></p>
<p>最多为满二叉树</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211528316.png" alt="" loading="lazy"></p>
</blockquote>
<p><strong>2017-4</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211558663.png" alt="image-20210726211558663" loading="lazy"></p>
<blockquote>
<p>B</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211658422.png" alt="image-20210726211658422" loading="lazy"></p>
</blockquote>
<p><strong>2017-5</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211724679.png" alt="image-20210726211724679" loading="lazy"></p>
<blockquote>
<p>B</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211824779.png" alt="image-20210726211824779" loading="lazy"></p>
</blockquote>
<p><strong>2018-4</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211910620.png" alt="image-20210726211910620" loading="lazy"></p>
<blockquote>
<p>满二叉树</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726212632926.png" alt="image-20210726212632926" loading="lazy"></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726212650654.png" alt="image-20210726212650654" loading="lazy"></p>
</blockquote>
<p><strong>2019-2</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211931557.png" alt="image-20210726211931557" loading="lazy"></p>
<blockquote>
<p>B</p>
</blockquote>
<p><strong>2020-3</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726211951141.png" alt="image-20210726211951141" loading="lazy"></p>
<blockquote>
<p>要存下任意一棵树，最坏情况</p>
<p>1+2 +4 +8 +16 = 31</p>
<p>2^5-1 = 31 </p>
</blockquote>
<p><strong>2020-4</strong></p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726213032648.png" alt="image-20210726213032648" loading="lazy"></p>
<blockquote>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726213120328.png" alt="image-20210726213120328" loading="lazy"></p>
</blockquote>
<h4 id="5-押题：AcWing-19"><a href="#5-押题：AcWing-19" class="headerlink" title="5. 押题：AcWing 19"></a>5. 押题：AcWing 19</h4><p><a href="">AcWing 19 二叉树的下一个节点</a></p>
<blockquote>
<p>线索二叉树。</p>
<p>算法<br>(模拟) O(h)O(h)<br>这道题目就是让我们求二叉树中给定节点的后继。</p>
<p>分情况讨论即可，如下图所示：</p>
<p>1.如果当前节点有右儿子，则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H；<br>2.如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。比如当前节点是D，则第一个满足是其father左儿子的节点是F，则C的father就是D的后继，即F是D的后继。</p>
<p><img src="https://gitee.com/li_zikang/lzk-image/raw/master/img/image-20210726215002976.png" alt="image-20210726215002976" loading="lazy"></p>
</blockquote>
<p>c++:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-comment">/**</span><br><span class="hljs-comment"> * Definition for a binary tree node.</span><br><span class="hljs-comment"> * struct TreeNode &#123;</span><br><span class="hljs-comment"> *     int val;</span><br><span class="hljs-comment"> *     TreeNode *left;</span><br><span class="hljs-comment"> *     TreeNode *right;</span><br><span class="hljs-comment"> *     TreeNode *father;</span><br><span class="hljs-comment"> *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) &#123;&#125;</span><br><span class="hljs-comment"> * &#125;;</span><br><span class="hljs-comment"> */</span><br><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span><br><span class="hljs-keyword">public</span>:<br>    <span class="hljs-function">TreeNode* <span class="hljs-title">inorderSuccessor</span><span class="hljs-params">(TreeNode* p)</span> </span>&#123;<br>        <span class="hljs-comment">// 1.如果当前节点有右儿子，则右子树中最左侧的节点就是当前节点的后继</span><br>        <span class="hljs-keyword">if</span>(p-&gt;right) &#123;<br>            p= p-&gt;right ;<br>            <span class="hljs-keyword">while</span>(p-&gt;left ) p=p-&gt;left;<br>            <span class="hljs-keyword">return</span> p;<br>        &#125;<br>        <br>        <span class="hljs-comment">// 2. 如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。</span><br>        <span class="hljs-keyword">while</span>(p-&gt;father&amp;&amp; p == p-&gt;father-&gt;right) p = p-&gt;father;<br>        <span class="hljs-keyword">return</span> p-&gt;father;<br>        <br>        <br>    &#125;<br>&#125;;<br></code></pre></td></tr></table></figure>

</div></section></article><div class="post-nav"><div class="post-nav-item"><a class="post-nav-prev" href="/2021/07/19/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_4_2/" rel="prev" title="数据结构 第5讲 二叉排序树、表达式树"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-left-s-line"></use></svg><span class="post-nav-text">数据结构 第5讲 二叉排序树、表达式树</span></a></div><div class="post-nav-item"><a class="post-nav-next" href="/2021/07/11/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/acwing/sjjg_3/" rel="next" title="数据结构 第三讲 栈与队列"><span class="post-nav-text">数据结构 第三讲 栈与队列</span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-right-s-line"></use></svg></a></div></div></div><div id="comment"><div class="comment-tooltip text-center"></div><div id="valine-container"></div><script src="https://cdn.jsdelivr.net/npm/valine@latest/dist/Valine.min.js"></script><script>function initValine() {
  const valineConfig = {"enable":true,"appId":"q22e7srtjevOqYmzusWCYIru-gzGzoHsz","appKey":"PMyzTxHUFQ77nPj1IWMcMDK3","placeholder":"畅所欲言！","avatar":null,"meta":["nick","mail","link"],"pageSize":10,"visitor":false,"highlight":true,"recordIP":false,"enableQQ":true,"el":"#valine-container","lang":"zh-cn"}
  valineConfig.path = window.location.pathname
  new Valine(valineConfig)
}
setTimeout(initValine, 1000)</script></div></main><footer class="sidebar-translate" id="footer"><div class="copyright"><span>&copy; 2020 – 2022 </span><span class="with-love" id="animate"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-cloud-line"></use></svg></span><span class="author"> 李子康</span></div><div class="powered"><span>由 <a href="https://hexo.io" target="_blank" rel="noopener">Hexo</a> 驱动 v4.2.1</span><span class="footer-separator">|</span><span>主题 - <a rel="noopener" href="https://github.com/YunYouJun/hexo-theme-yun" target="_blank"><span>Yun</span></a> v0.9.2</span></div><div class="live_time"><span>本博客已萌萌哒地运行</span><span id="display_live_time"></span><span class="moe-text">(●'◡'●)</span><script>function blog_live_time() {
  window.setTimeout(blog_live_time, 1000);
  const start = new Date('2020-07-05T00:00:00');
  const now = new Date();
  const timeDiff = (now.getTime() - start.getTime());
  const msPerMinute = 60 * 1000;
  const msPerHour = 60 * msPerMinute;
  const msPerDay = 24 * msPerHour;
  const passDay = Math.floor(timeDiff / msPerDay);
  const passHour = Math.floor((timeDiff % msPerDay) / 60 / 60 / 1000);
  const passMinute = Math.floor((timeDiff % msPerHour) / 60 / 1000);
  const passSecond = Math.floor((timeDiff % msPerMinute) / 1000);
  display_live_time.innerHTML = " " + passDay + " 天 " + passHour + " 小时 " + passMinute + " 分 " + passSecond + " 秒";
}
blog_live_time();
</script></div><div id="busuanzi"><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><span id="busuanzi_container_site_uv" title="总访客量"><span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-user-line"></use></svg></span><span id="busuanzi_value_site_uv"></span></span><span class="footer-separator">|</span><span id="busuanzi_container_site_pv" title="总访问量"><span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-eye-line"></use></svg></span><span id="busuanzi_value_site_pv"></span></span></div></footer><a class="hty-icon-button" id="goUp" aria-label="back-to-top" href="#"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-up-s-line"></use></svg><svg class="progress-circle-container" viewBox="0 0 100 100"><circle class="progress-circle" id="progressCircle" cx="50" cy="50" r="48" fill="none" stroke="black" stroke-width="2" stroke-linecap="round"></circle></svg></a></div><script defer src="/js/utils.js"></script><script defer src="/js/hexo-theme-yun.js"></script><script defer src="/js/player.js"></script></body></html>